#include<cstdio>//C++中stdio.h用这个代替
#include<cstdlib>
typedef int ElemType;
typedef struct LNode
{
    ElemType data;//存放元素值
    struct LNode *next;//指向后继节点
}LinkNode;//单链表结构类型
//头插法建立单链表(逆序)
void CreatListF(LinkNode *&L,ElemType arr[],int n) {
    LinkNode *s;
    L =(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;//创建头结点，将其next域置为NULL
    for (int i = 0; i < n; i++)
    {
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=arr[i];//创建数据节点s
        s->next=L->next;//将节点s插入原首节点前，头节点后
        L->next=s;
    }
}
//尾插法建立单链表(顺序）
void CreatListR(LinkNode *&L,ElemType arr[],int n)
{
    LinkNode *s,*r;
    L=(LinkNode *)malloc(sizeof(LinkNode));//创建头结点
    r=L;//r始终指向尾结点，初始时指向头结点
    for(int i=0;i<n;i++)//循环建立数据节点
    {
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=arr[i];//创建数据节点s
        r->next=s;//将节点s插入节点r之后
        r=s;
    }
    r->next=NULL;//将尾结点的指针域置为NULL
}
//初始化线性表
void InitList(LinkNode *&L)
{
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;
}
//销毁线性表
void DestroyList(LinkNode *&L)
{
    LinkNode *pre=L,*p=L->next;//pre指向结点p的前驱结点
    while(p!=NULL)//遍历单链表L
    {
        free(pre);//释放pre结点
        pre=p;//pre，p同步后移一个结点
        p=p->next;
    }
    free(pre);//循环结束时p为NULL，pre指向尾结点，释放他
}
//判断线性表是否为空表
bool ListEmpty(LinkNode *L)
{
    return(L->next==NULL);
}
//求线性表长度
int ListLength(LinkNode *L)
{
    int n=0;
    LinkNode *p=L;//p指向头结点，n置为0（即头结点的序号为0）
    while(p->next!=NULL)
    {
        p=p->next;
        n++;
    }
    return n;//循环结束，p指向尾结点，其序号n为结点的个数
}
//输出线性表
void DispList(LinkNode *L)
{
    LinkNode *p=L->next;//p指向首结点
    while(p!=NULL)//p不为NULL，输出p结点的data域
    {
        printf("%d ",p->data);
        p=p->next;//p移动下一个结点
    }
    printf("\n");
}
//按序号求线性表中的元素
bool GetElem(LinkNode *L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L;//p指向头结点，j置为0（即头结点的序号为0）
    if(i<=0)return false;//i错误返回假
    while(p!=NULL&&j<i)//查找第i个结点p
    {
        j++;
        p=p->next;
    }
    if(p==NULL)//不存在第i个数据节点，返回false
        return false;
    else//存在第i个数据结点，返回true
    {
        e=p->data;
        return true;
    }
}
//按元素值查找
int LocateElem(LinkNode *L,ElemType e)
{
    int i=1;
    LinkNode *p=L->next;//p指向首结点，i置为1（即首结点的序号为1）
    while(p!=NULL&&p->data!=e)//查找data值为e的结点，其序号为i
    {
        p=p->next;
        i++;
    }
    if(p==NULL)//不存在值为e的结点，返回0
        return 0;
    else //存在值为e的结点，返回其逻辑序号i
        return i;
}
//插入数据元素
bool ListInsert(LinkNode *&L,int i,ElemType e)
{
    int j=0;
    LinkNode *p=L,*s;//p指向头结点，j置为0（即头结点的序号为0）
    if(i<=0)return false;//i错误返回假
    while(j<i-1&&p!=NULL)//查找第i-1个结点p
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return true;
    }
}
//删除数据元素
bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L,*q;
    if(i<=0)return false;
    while(j<i-1&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        q=p->next;
        if(q==NULL)return false;
        e=q->data;
        p->next=q->next;
        free(q);
        return true;
    }
}
//单链表应用示例
//将一个带头结点的单链表L=(a1,b1,a2,b2...)拆分为两个单链表L1=(a1,a2...),L2=(bn,bn-1..),L1使用L的头结点
void split(LinkNode *&L,LinkNode *&L1,LinkNode *&L2)
{
    LinkNode *p=L->next,*q,*r1;
    L1=L;
    r1=L1;
    L2=(LinkNode *)malloc(sizeof(LinkNode));
    L2->next=NULL;
    while(p!=NULL)
    {
        r1->next=p;
        r1=p;
        p=p->next;
        q=p->next;
        p->next=L2->next;
        L2->next=p;
        p=q;
    }
    r1->next=NULL;
}
//删除链表中元素最大值
void DelMaxNode(LinkNode *&L)
{
    LinkNode *p=L->next,*pre=L,*maxp=p,*maxpre=pre;
    while(p!=NULL)
    {
        if(maxp->data<p->data)
        {
            maxp=p;
            maxpre=pre;
        }
        p=p->next;
        pre=pre->next;
    }
    maxpre->next=maxp->next;
    free(maxp);
}
//实现所有数据结点按data域递增排序
void sort(LinkNode *&L)
{
    LinkNode *p,*pre,*q;
    p=L->next->next;
    L->next->next=NULL;
    while(p!=NULL)
    {
        q=p->next;
        pre=L;
        while(pre->next!=NULL&&pre->next->data<p->data)
        {
            pre=pre->next;
        }
        p->next=pre->next;
        pre->next=p;
        p=q;
    }
}
int main()
{
    LinkNode *L,*L1,*L2;
    ElemType arr[]={1,2,3,4,5,6},e;
    InitList(L);
    CreatListF(L,arr,6);
    sort(L);
    DispList(L);
    DestroyList(L);
    return 0;
}